package L619;

import util.ListNode;

/**
 * @program: javase
 * @description: 排序链表
 * @author: luolidong
 * @create: 2021-06-19 19:34
 * @version: 1.0
 */
public class SortList {
    public ListNode sortList(ListNode head) {
        return merge(head, null);
    }

    public ListNode merge(ListNode head, ListNode tail) {
        if (head == null) return null;
//         两个元素，直接断开
        if (head.next == tail) {
            head.next = null;
            return head;
        }
//         求链表中点
        ListNode mid = getMidNode(head, tail);
        ListNode left = merge(head, mid);
        ListNode right = merge(mid, tail);

        return mergeSort(left, right);
    }

    private ListNode mergeSort(ListNode head1, ListNode head2) {
        if (head1 == null && head2 == null) return null;
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }

    //     1 2 3 4 5
    public ListNode getMidNode(ListNode head, ListNode tail) {
        ListNode fast = head, slow = head;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode listNode = new SortList().sortList(ListNode.build());
        System.out.println(listNode);
    }
}
